package com.example.spring5.datastruct.linkedlist;

/**
 * @Author: Hu Rui
 * @Date: 2021/11/13 12:31
 */
public class IsCycle {

    /**
     * 判断链表是否有环
     *
     * @param node
     * @return
     */
    public static boolean isCycle(Node node) {
        Node slow = node, fast = node;
        while (slow != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 计算环的长度 第一次相遇到第二次相遇之间的循环次数就是环的长度
     *
     * @param node
     * @return
     */
    public static int cycleLength(Node node) {
        var meetCount = 0;
        var length = 0;
        Node slow = node, fast = node;
        while (slow != null && fast.next != null) {
            if (meetCount == 1) {
                length++;
            } else if (meetCount == 2) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                meetCount++;
            }
        }
        return length;
    }

    /**
     * 查找如环口
     * 1、找到p1和p2第一次相遇的点记为p3。
     * 2、让p4从头节点开始走，p3也用相同速度走。
     * 3、p3和p4第一次相遇的点就是入环点。
     * @param head
     * @return
     */
    public static Node findEnterNode(Node head) {
        Node p1 = head,p2 = head;
        Node p3 = null;
        while (p1 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                p3 = p1;
                break;
            }
        }
        Node p4 = head;
        while (p3 != null && p3 != p4) {
            p3 = p3.next;
            p4 = p4.next;
        }
        return p3;
    }


    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return this.data+"";
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(5);
        Node node2 = new Node(3);
        Node node3 = new Node(7);
        Node node4 = new Node(2);
        Node node5 = new Node(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node5;
        System.out.println(findEnterNode(node5));
    }
}
